package com.leetcode.partition2;

import java.util.ArrayList;
import java.util.List;

/**
 * @author `RKC`
 * @date 2021/8/13 22:17
 */
public class LC131分割回文串 {

    public static List<List<String>> partition(String s) {
        List<List<String>> result = new ArrayList<>();
        backtracking(result, new ArrayList<>(), 0, s);
        return result;
    }

    public static void main(String[] args) {
        System.out.println(partition("aab"));
    }

    private static void backtracking(List<List<String>> result, List<String> path, int startIndex, String str) {
        //如果起始位置已经大于s的大小，说明已经找到了一组切割方案
        if (startIndex >= str.length()) {
            result.add(new ArrayList<>(path));
            return;
        }
        for (int i = startIndex; i < str.length(); i++) {
            if (!isPalindrome(str, startIndex, i)) continue;
            path.add(str.substring(startIndex, i + 1));
            backtracking(result, path, i + 1, str);
            path.remove(path.size() - 1);
        }
    }

    public static boolean isPalindrome(String s, int start, int end) {
        char[] array = s.toCharArray();
        for (int i = start, j = end; i < j; i++, j--) {
            if (array[i] != array[j]) return false;
        }
        return true;
    }
}
